package com.algorithm.impl.string;

/**
 * @author: ZhouBert
 * @date: 2019/9/27
 * @description:	字符串匹配的RK算法
 * RK算法是由Rabin和Karp共同提出的一个算法。
 * 　　RK算法是对BF算法的一个改进：在BF算法中，每一个字符都需要进行比较，并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中，就尝试只进行一次比较来判定两者是否相等。
 * 　　RK算法也可以进行多模式匹配，在论文查重等实际应用中一般都是使用此算法。
 * 　　时间复杂度：O（MN）（实际应用中往往较快，期望时间为O（M+N））
 * RK算法的基本思想
 * 　　TODO:使用HASH比较。如果两个字符串hash后的值不相同，则它们肯定不相同；如果它们hash后的值相同，它们不一定相同。
 * 　　RK算法的基本思想就是：将模式串P的hash值跟主串T中的每一个长度为|P|的子串的hash值比较。如果不同，则它们肯定不相等；如果相同，由于哈希冲突存在，也需要按照BF算法诸位比较。
 */
public class RabinKarpRK {



	public static void main(String[] args) {

	}
}
